//https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tqId=23294&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D13
//思路1:递归思想-后序遍历实现（必须掌握！！！）
//思路2:队列，层序遍历，宽度优先遍历

#include <iostream>
#include <math.h>
#include <array>
#include <set>
#include <queue>

using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};


//时间复杂度：O(n)，遍历整棵树;
// 空间复杂度：O（n），最差情况下，退化成链表，递归深度最大为n;
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {

		if (pRoot == nullptr) return 0;

		int l_len = TreeDepth(pRoot->left);

		int r_len = TreeDepth(pRoot->right);

		return std::max(r_len , l_len) + 1;
    }
};


class Solution2 {
public:
    int maxDepth(TreeNode* root) {
        //空节点没有深度
        if(root == NULL)
            return 0;
        //队列维护层次后续节点
        queue<TreeNode*> q;
        //根入队
        q.push(root);
        //记录深度
        int res = 0;
        //层次遍历
        while(!q.empty()){
            //记录当前层有多少节点
            int n = q.size();
            //遍历完这一层，再进入下一层
            for(int i = 0; i < n; i++){
                TreeNode* node = q.front();
                q.pop();
                //添加下一层的左右节点
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            //深度加1
            res++;
        }
        return res;
    }
};